package main

import (
	"fmt"
	"math"
	"time"
)

func rob(nums []int) int {
	// if len(nums) <= 0 {
	// 	// fmt.Println("return")
	// 	return 0
	// }
	// count := len(nums)
	// max := 0
	// result := 0
	// for i := 0; i < count; i++ {
	// 	if nums[i] > nums[max] {
	// 		max = i
	// 	}
	// }
	// result += nums[max]
	// // fmt.Println(max)

	// end := max - 1
	// left := 0
	// if max-1 < 0 {
	// 	left = 0
	// } else {
	// 	left = rob(nums[:end])
	// }

	// result += left
	// // fmt.Println("nums[:max]", nums[:end])

	// start := max + 2
	// right := 0
	// if start >= count {
	// 	right = 0
	// } else {
	// 	right = rob(nums[start:])
	// }
	// // fmt.Println("nums[max+1:]", nums[start:])

	// result += right

	// // fmt.Println()
	// return result

	if nums == nil || len(nums) == 0 {
		return 0
	}
	length := len(nums)

	dp := [][2]int{{0, nums[0]}}
	for i := 1; i < length; i++ {
		// array := []int{}
		// notStolen := 0
		// if dp[i-1][0] > dp[i-1][1] {
		// 	notStolen = dp[i-1][0]
		// } else {
		// 	notStolen = dp[i-1][1]
		// }
		notStolen := math.Max(float64(dp[i-1][0]), float64(dp[i-1][1]))
		stolen := dp[i-1][0] + nums[i]
		// array = append(array, int(notStolen))
		// array = append(array, stolen)
		// dp = append(dp, array)
		dp = append(dp, [2]int{int(notStolen), stolen})
		// fmt.Println(dp)
		// dp[i][0] = int(notStolen)
		// dp[i][1] = stolen

	}

	return int(math.Max(float64(dp[length-1][0]), float64(dp[length-1][1])))
}

func main() {
	start := time.Now()
	nums := []int{1, 3, 9, 0, 5}

	dec := rob(nums)
	cost := time.Since(start)
	fmt.Println(dec)
	fmt.Println(cost)
}
